"""
https://leetcode.cn/problems/reverse-linked-list-ii/description/

92. 反转链表 II
已解答
中等
相关标签
相关企业
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 

示例 1：


输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]
 

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
 

进阶： 你可以使用一趟扫描完成反转吗？
"""
# Definition for singly-linked list.
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    """
    仍然是交通信号灯的思路，只是控制索引

    N-1-2-3-4-5-N
    N-1-4-3-2-5-N

    不进阶了，直接用list解决
    没有必要为了难而难，就像没有必要做初中题目时发现用高中的知识更容易解决，但偏偏就用初中的知识。

    """
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if head is None:
            return None
        temp=head
        node_list=[temp]
        while temp.next is not None:
            temp=temp.next
            node_list.append(temp)

        l=left-1
        r=right-1
        while l<r:
            node_list[l],node_list[r]=node_list[r],node_list[l]
            l+=1
            r-=1

        for i in range(left-1-1,right-1+1):
            if i==-1:
                continue
            node_list[i].next=node_list[i+1] if i+1<len(node_list) else None

        return node_list[0]

            

if __name__=='__main__':
    s=Solution()
    head=ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))
    left=2
    right=4
    res=s.reverseBetween(head,left,right)
    while res is not None:
        print(res.val)
        res=res.next